package ink.lovejinhu.swardToOffer;

/**
 * @author jinhu
 * created 2021-08-11 8:02
 */
public class Offer_004 {
//    public static void main(String[] args) {
//        int[][] res = {{1, 4, 7, 11, 15},
//                {2, 5, 8, 12, 19},
//                {3, 6, 9, 16, 22},
//                {10, 13, 14, 17, 24},
//                {18, 21, 23, 26, 30}
//        };
//        int target0 = 5;
//        int target1 = 20;
//        Offer_004 offer_004 = new Offer_004();
//        boolean numberIn2DArray = offer_004.findNumberIn2DArray(res, target0);
//        System.out.println(numberIn2DArray);
//        boolean numberIn2DArray1 = offer_004.findNumberIn2DArray(res, target1);
//        System.out.println(numberIn2DArray1);
//    }

    /**
     * 二维数组中的查找
     *
     * @param matrix
     * @param target
     * @return
     */
    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0) {
            return false;
        }
        int rowLeft = 0;
        int rowRight = matrix.length;
        int columnLeft = 0;
        int columnRight = matrix[0].length;
        return this.dfs(matrix, target, rowLeft, rowRight - 1, columnLeft, columnRight - 1);

    }

    public boolean dfs(int[][] martrix, int target, int rowLeft, int rowRight, int columnLeft, int columnRight) {
        if (rowLeft > rowRight || columnLeft > columnRight) {
            return false;
        }
        int rowMid = rowLeft + rowRight >> 1;
        int columnMid = columnLeft + columnRight >> 1;
        System.out.println(martrix[rowMid][columnMid]);
        if (martrix[rowMid][columnMid] == target) {
            System.out.println(martrix[rowMid][columnMid]);
            return true;
        } else if (martrix[rowMid][columnMid] > target) {
            return dfs(martrix, target, rowLeft, rowMid - 1, columnLeft, columnMid - 1) ||
                    dfs(martrix, target, rowMid, rowRight, columnLeft, columnMid - 1) ||
                    dfs(martrix, target, rowLeft, rowMid - 1, columnMid, columnRight)
                    ;

        } else {
            return dfs(martrix, target, rowMid + 1, rowRight, columnMid + 1, columnRight) ||
                    dfs(martrix, target, rowMid, rowRight, columnLeft, columnMid - 1) ||
                    dfs(martrix, target, rowLeft, rowMid - 1, columnMid, columnRight)
                    ;
        }

    }

    /**
     * 从右上角开始
     *
     * @param matrix
     * @param target
     * @return
     */
    public boolean findNumberIn2DArray1(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0) {
            return false;
        }
        int row = 0;
        int column = matrix[0].length-1;
        while (row < matrix.length && column >= 0) {
            if (matrix[row][column] == target) {
                return true;
            } else if (matrix[row][column] > target) {
                column--;
            } else {
                row++;
            }
        }
        return false;
    }
}
